package t_509

func fib(n int) int {

	if n < 2 {
		return n
	}

	result := fib(n-2) + fib(n-1)

	return result
}

func fibUp(n int) int {

	if n < 2 {
		return n
	}

	cache := make(map[int]int)
	cache[0] = 0
	cache[1] = 1

	for start := 2; start <= n; start++ {
		cache[start] = cache[start-2] + cache[start-1]
	}

	return cache[n]
}
